package org.datrie;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author ariel.piechotka
 * */
public class Datrie {

	public static List<Character> alphabet = getAlphabet();
	private static String tailStr = "";
	public static byte[] tail;
	public static byte[] bc;
	private static final int BASE_MASK = 0x003FFFFF;
	private static final int SPLIT_MASK = 0x00400000;
	private static final int LEAF_MASK = 0x00800000;

	public static void createTrie(Node node, List<String> words, int level) {
		for (char c : alphabet) {
			List<String> subwords = getAllWordsStartingWith(c, words);
			if (!subwords.isEmpty()) {
				Node child = new Node();
				node.children.add(child);
				child.data = c;
				child.parent = node;
				if (level <= 1)
					System.out.println("Level: " + level + ", c: " + c);
				createTrie(child, subwords, level + 1);
			}
		}
	}

	public static void transformToReducedTrie(Node node) {
		for (Node child : node.children)
			if (child.isLeaf()) {
				Node current = child;
				String s = "";
				while (!current.hasSiblings() && !current.isRoot()) {
					s = current.data + s;
					current = current.parent;
				}
				current.tail = s;
			} else
				transformToReducedTrie(child);
		for (Node child : node.children)
			if (child.tail != null)
				child.children.clear();
	}

	public static void transformToDescendedTrie(Node node) {
		for (Node child : node.children) {
			if (child.isReducible())
				child.reduce();
			transformToDescendedTrie(child);
		}
	}

	public static void makeUnifiedTail(Node node) {
		for (Node child : node.children) {
			if (child.isLeaf()) {
				int tailp = tailStr.indexOf(child.tail);
				if (tailp == -1) {
					child.tailp = tailStr.length();
					tailStr += child.tail;
				} else
					child.tailp = tailp;
				child.tail = null;
			} else
				makeUnifiedTail(child);
		}
	}

	public static void setBase(Node node) {
		node.setBase();
		for (Node child : node.children)
			if (!child.isLeaf())
				setBase(child);
	}

	public static void buildBinaryArrays(Node node) {
		tail = new byte[tailStr.length()];
		for (int i = 0; i < tailStr.length(); i++)
			tail[i] = (byte) tailStr.charAt(i);

		bc = new byte[4 * (Collections.max(Node.occupiedIds) + 1)];
		Queue<Node> qNodes = new LinkedList<Node>();
		Node tmp;
		qNodes.add(node);
		while (!qNodes.isEmpty()) {
			tmp = (Node) qNodes.poll();

			int bcWord = 0;
			bcWord |= BASE_MASK & (tmp.isLeaf() ? tmp.tailp : tmp.base);
			bcWord |= tmp.split ? SPLIT_MASK : 0;
			bcWord |= tmp.isLeaf() ? LEAF_MASK : 0;
			bcWord |= ((int) (byte) (char) (tmp.data == null ? '#' : tmp.data)) << 24;
			int pos = (tmp.id == null ? 0 : tmp.id) * 4;
			bc[pos] = (byte) ((bcWord & 0xFF000000) >> 24);
			bc[pos + 1] = (byte) ((bcWord & 0x00FF0000) >> 16);
			bc[pos + 2] = (byte) ((bcWord & 0x0000FF00) >> 8);
			bc[pos + 3] = (byte) (bcWord & 0x000000FF);

			for (Node child : tmp.children)
				qNodes.add(child);
		}
	}

	/**
	 * Selecciona en la lista <code>words</code>, todas las palabras que
	 * comiencen con el caracter <code>c</code>, devolviendo una lista con los
	 * sufijos de esas palabras (la parte que va despues de la letra)
	 * 
	 * @param c
	 * @param words
	 * @return
	 */
	private static List<String> getAllWordsStartingWith(Character c, List<String> words) {

		int first = binarySearchFirstWithInitial(words, c);
		int last = binarySearchLastWithInitial(words, c);
		if (first == -1)
			return new ArrayList<String>();

		List<String> subwords = new ArrayList<String>(words.subList(first, last + 1));
		for (int i = 0; i < subwords.size(); i++)
			subwords.set(i, subwords.get(i).substring(1));
		return subwords;
	}

	private static List<Character> getAlphabet() {
		List<Character> alphabet = new ArrayList<Character>();
		alphabet.add('#');
		for (char c = 'A'; c <= 'Z'; c++)
			alphabet.add(c);
		alphabet.add('_');
		for (char c = 'a'; c <= 'z'; c++)
			alphabet.add(c);
		return alphabet;
	}

	/**
	 * Busca y devuelve la palabra de menor indice que empiece con el caracter c
	 * 
	 * @param a
	 * @param c
	 * @return
	 */
	private static int binarySearchFirstWithInitial(List<String> a, Character c) {
		int low = 0;
		int high = a.size() - 1;
		int mid;

		while (low <= high) {
			mid = (low + high) / 2;
			if (a.get(mid).startsWith(c.toString()) && (mid == 0 || !a.get(mid - 1).startsWith(c.toString())))
				return mid;
			else if (a.get(mid).compareTo(c.toString()) < 0)
				low = mid + 1;
			else
				high = mid - 1;
		}
		return -1;
	}

	/**
	 * Busca y devuelve la palabra de mayor indice que empiece con el caracter c
	 * 
	 * @param a
	 * @param c
	 * @return
	 */
	private static int binarySearchLastWithInitial(List<String> a, Character c) {
		int low = 0;
		int high = a.size() - 1;
		int mid;

		while (low <= high) {
			mid = (low + high) / 2;
			if (a.get(mid).startsWith(c.toString())
					&& (mid == a.size() - 1 || !a.get(mid + 1).startsWith(c.toString())))
				return mid;
			else if (a.get(mid).compareTo(c.toString() + Character.MAX_VALUE) < 0)
				low = mid + 1;
			else
				high = mid - 1;
		}
		return -1;
	}
}
